package com.yaoli.ajob;

/**
 * Created by will on 2017/4/29.
 */
public class _343_IntegerBreak {
    public static void main(String[] args) {
        _343_IntegerBreak integerBreak = new _343_IntegerBreak();

        integerBreak.integerBreak(20);
    }
    // 3 3 3 3 3 3 4
    //n = 20
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        //从2开始 到20
        for(int i = 2; i <= n; i ++) {

            //从1 到 i
            for(int j = 1; j < i; j ++) {

                //比较 j 和 dp【j】
                dp[i] = Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i - j, dp[i - j])));
            }
        }
        return dp[n];
    }
}
